package com.itheima.datastructure.linkedlist;

/**
 * 有序链表去重，例如[1, 1, 2, 3, 3, 4, 4, 4]  删除后为 [1, 2, 3, 4]
 */
public class E04Leetcode83 {

    public ListNode deleteDuplicates0(ListNode head) {
        if (null == head || null == head.next) {
            return head;
        }
        // 创建哨兵节点
        ListNode sentinel = new ListNode(-1, head);
        //前一个节点
        ListNode pre = sentinel;
        //当前节点
        ListNode cur = head;
        while (cur != null) {
            if (cur.val > pre.val) {
                //pre向后移动
                pre = pre.next;
                //cur向后移动
                cur = cur.next;
            } else {
                //删除cur
                pre.next = cur.next;
                //cur向后移动
                cur = cur.next;
            }
        }
        return sentinel.next;
    }


    public ListNode deleteDuplicatesR(ListNode head) {
        ListNode sentinel = new ListNode(-1, head);
        return recursion(sentinel);

    }


    /**
     * 递归实现
     *
     * @param cur
     * @return
     */


    public ListNode recursion(ListNode cur) {
        if (cur == null || cur.next == null) {
            return cur;
        }
        recursion(cur.next);
        if (cur.val == cur.next.val) { //如果当前节点值等于下一个节点值
            //则删除下一节点
            cur.next = cur.next.next;
        }


        //例：1->1->2->3->3->null
        //--cur<3>[3->3->null]，符合删除条件 变为[3->null]
        //--cur<2>[2->3->null]
        //--cur<1>[1->2->3->null]
        //--cur<1>[1->1->2->3->null] ,符合删除条件 ，变为 [1->2->3->null]

        //返回下一个节点
        return cur.next;

    }


    // 方法2
    public ListNode deleteDuplicates(ListNode cur) {
        if (cur == null || cur.next == null) {
            return cur;
        }
        if (cur.val == cur.next.val) {
            //如果当前节点的值等于下一个节点的值
            ListNode next = deleteDuplicates(cur.next);
            //返回下一个节点(删除当前)
            return next;
        } else {
            ListNode next = deleteDuplicates(cur.next);
            //更新自身的next
            cur.next = next;
            //返回自身
            return cur;
        }
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 1, 2, 3, 3, 4, 4, 4);
        System.out.println(head);
        System.out.println(new E04Leetcode83().deleteDuplicates(head));
    }
}
